package bfsAndDfs

/*
基于DFS的拓扑排序

时间复杂度：O(n+m) n是总课程数，m是先修课程关系数(邻接表大小)
空间复杂度：O(n+m) 对n个节点进行dfs，每个节点只遍历该节点的邻接边（所有边总数为m条）
*/
func canFinish(numCourses int, prerequisites [][]int) bool {
	var (
		result  []int                       // 存储拓扑排序结果
		edges   = make([][]int, numCourses) // 构造邻接表(每一行存储一个节点到他所指向的所有节点的映射)
		dfs     func(u int)                 // 从节点u开始进行dfs
		visited = make([]int, numCourses)   // 存储节点的状态，0表示未搜索，1表示搜索中，2表示搜索完成
		valid   = true                      // 表示是否能完成拓扑排序（如不能完成表示有环）
	)

	dfs = func(u int) {
		// 先将节点u状态设置为1，表示开始搜索（搜索中）
		visited[u] = 1
		// 遍历节点u的所有邻接节点
		for _, v := range edges[u] {
			// 如果邻接节点状态为0（未搜索），则dfs，dfs后返回该节点，需要先判断dfs后valid是否为true，为false直接返回
			if visited[v] == 0 {
				dfs(v)
				if !valid {
					return
				}
			} else if visited[v] == 1 {
				// 如果正在对某一个节点A进行dfs，在dfs的过程中遇到节点值==1,则说明存在环，因为如果没有环的话，dfs遇到的节点应该全是0或者2
				valid = false
				return
			}
		}
		// 本次dfs结束，将dfs最开始的节点设置为2（表示已搜索完）
		visited[u] = 2
		// 将搜索完成的节点存入result，之后对result逆序输出即为拓扑排序的顺序（因为在一次dfs中，第一个节点要在后面所有节点搜索完之后才会设置为2
		// 所以第一个节点将被最后放入result中，所以需要逆序输出）
		result = append(result, u)
	}

	// 构造邻接表
	for _, info := range prerequisites {
		edges[info[1]] = append(edges[info[1]], info[0])
	}
	// 遍历所有节点，如果节点状态为0，则进行dfs
	for i := 0; i < numCourses; i++ {
		if visited[i] == 0 {
			dfs(i)
		}
	}
	return valid
}

/*
kahn算法（基于BFS的拓扑排序）

时间复杂度:O(n+m) 对图进行广度优先搜索的时间复杂度
空间复杂度:O(n+m) 邻接表
 */
func canFinish1(numCourses int, prerequisites [][]int) bool {
	var (
		result   []int // 存储拓扑排序结果
		edges    = make([][]int, numCourses)
		queue    []int
		inDegree = make([]int, numCourses)
	)

	// 构造邻接表
	for _, info := range prerequisites {
		edges[info[1]] = append(edges[info[1]], info[0])
		// 统计各节点入度
		inDegree[info[0]]++
	}

	// 将入度为0的节点放入队列
	for i, v := range inDegree {
		if v == 0 {
			queue = append(queue, i)
		}
	}

	// 从入度为0的节点开始bfs
	for len(queue) != 0 {
		e := queue[0]
		queue = queue[1:]
		result = append(result, e)
		// 删除e后，将e的邻居节点的入度-1，最后将入度为0的节点放入队列
		for _, v := range edges[e] {
			inDegree[v]--
			if inDegree[v] == 0 {
				queue = append(queue, v)
			}
		}
	}
	// 判断最后result中节点是否等于图中所有节点
	// BFS的result中的节点顺序是拓扑排序，DFS是拓扑排序的逆序
	return len(result) == numCourses
}
